软考真题
第4题

阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。

【说明】

设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为ti,要求确定一个调度方案,使得完成所有任务所需要的时间最短。

假设任务已经按照其运行时间从大到小顺序。算法基于最长运行时间作业优先的策略;按顺序先把每个任务分配到一台机器上,然后将剩余的任务依次放入空闲的机器。

【C代码】

下面是算法的C语言实现。

(1) 常量和变量说明

m:机器数

n:任务数

t[]:输入数组,长度为n,其中每个元素表示任务的运行时间,下标从0开始

s[][]:二维数组,长度为m*n,下标从0开始,其中元素s[i][j]表示机器i运行的任务j的编号

d[]:数组,长度为m,其中元素d[i]表示机器i的运行时间,下标从0开始

count[]:数组,长度为m,下标从0开始,其中元素count[i]表示机器i的运行任务数

i:循环变量

j:循环变量

k:临时变量

max:完成所有任务的时间

min:临时变量

(2) 函数schedule

【问题:4.1】

根据说明和c代码,填充C代码中的空(1)~(4)。

【问题:4.2】根据说明和C代码,该问题采用了 (5) 算法设计策略,时间复杂度为 (6) (用O符号表示)。
【问题:4.3】考虑实例m=3(编号0~2),n=7(编号0~6),各任务的运行时间为{16,14,6,5,4,3,2}。
则在机器0、1和2上运行的任务分别为(7)、(8)和(9)(给出任务编号)。从任务开始运行到完成所需要的时间为 (10) 。
2013年 上半年 下午试卷 案例
正确答案:
你的答案:
请先在App中激活(应用市场搜“软考真题”)
知识点:
试卷:
2013年 上半年 下午试卷 案例

笔记

村头小芳

请先在App中激活(应用市场搜“软考真题”)

2020-10-19


请先在App中激活(应用市场搜“软考真题”)

2019-11-04


请先在App中激活(应用市场搜“软考真题”)

2019-11-03


幽竹

请先在App中激活(应用市场搜“软考真题”)

2023-11-01


答题卡
加油
纠错
得分:0